i can't seem to understand the logic behind linked lists :|

**Axel** · 10-13-2006

Ok i've made my code really simplistic to tackle the problem i'm having currently of understanding how linked lists work. I only know what happens until a new node is added (i.e. 1) but i can't seem to understand what happens AFTER that i.e if there are more than 1 nodes. So i've highlighted the bits where i exactly can't understand. Hopefully someone can explain it step by step.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct charNode
{
   char petName[12];

   struct charNode *next;
};

typedef struct charNode charNode;

void addElement(charNode **start, char *petName);
void printList(charNode *start);
charNode* newNode(char *petName);
void getString(charNode *start);

int main()
{
   charNode *start = NULL;

   getString(start);
  
   return 0;
}


void getString(charNode *start)
{

     addElement(&start, "(1)Cat");
     addElement(&start, "(2)Dog");
     addElement(&start, "(3)Horse");
   
     printList(start);
}

void addElement(charNode **start, char *petName)
{

   charNode *temp,*prev, *loc;
   int i;

   temp = newNode(petName);


   if (*start == NULL)
   {
      *start = temp;
   }

   else
   {
      loc = *start;
      prev = NULL;

       for (i=0; loc != NULL; i++)
       {
      	 	printf("%d", i);
      	 	printf(" %s ", loc->petName);
           	prev = loc;
			loc = loc->next;
        }
		printf("\n");
		printf("\n");

      temp->next = loc;
	  prev->next = temp;
   }

}


charNode* newNode(char *petName)
{

   charNode *temp;

   temp = (charNode *) malloc(sizeof(charNode));
   if (temp == NULL)
   {
      printf("WARNING - Memory allocation error\n");
      exit(EXIT_FAILURE);
   }


  strcpy(temp->petName, petName);


   temp->next = NULL;

   return temp;
}


void printList(charNode *start)
{

   while (start != NULL)
   {

      printf("%s\n", start->petName);
      start = start->next;
   }
}

**yxunomei** · 10-14-2006

Hi,

first of all, on the typdef line, do something actually useful

hint :

Code:

typedef char* String

here's the stepwise evaluation for

Code:

void getString(charNode *start)
{

     addElement(&start, "(1)Cat");
     addElement(&start, "(2)Dog");
     addElement(&start, "(3)Horse");
   
     printList(start);
}

on the first call of add Element, *start is NULL (look at main() )

so according to your function, addElement returns start (by reference) by calling newNode

Code:

   if (*start == NULL)
   {
      *start = temp;
   }

** tips : instead of using strcpy, use strncpy ... strcpy doesn't have any check for buffer overflow.... to use strncpy :

Code:

strncpy(char *destination, char *source, bufferLength)
in your case :
strncpy(temp->petName, petName, 12);

so far, *start has a string "(1)Cat" according to

Code:

addElement(&start, "(1)Cat");

on the second call: (the part u actually asked

)

Code:

addElement(&start, "(2)Dog");

before:

Code:

temp = newNode(petName); // making temp an element with new string in it
prev = NULL; // nowhere
loc = *start 
/* loc has the same address as *start (ie harshly the same as saying 
 * int *i, a = 10;
 * i = &a;
 */
"(1)Cat" -> NULL
   ^
 loc

1st iteration :

Code:

prev = loc;
"(1)Cat" -> NULL
   ^
(prev & loc)
loc = loc->next // loc becomes NULL
"(1)Cat" -> NULL
   ^         ^
 prev      loc       

the nullity of loc terminates the for loop and notice here how prev is actually used to store the last item in the list

then
temp->next = loc; // assigning the next of the temp to be NULL, since loc is null... 
** tips : I don't personally think this is neccessary, since newNode has done this for you (Tested)

prev->next = temp; // simply appending the new element to the end of the old list
}

Hope dat helps

**jafet** · 10-14-2006

You don't understand the code, or the concept?

If it's the latter, you might enjoy [url=http://www.cprogramming.com/tutorial/lesson15.html]this[/rul] and/or this.

**Axel** · 10-14-2006

Originally Posted by yxunomei

Hi,

Code:

prev = loc;
"Panda" -> NULL
   ^

ok this confuses me. loc is pointing to start
hence: loc = *start; and not null is this an error?

Originally Posted by jafet

You don't understand the code, or the concept?

If it's the latter, you might enjoy [url=http://www.cprogramming.com/tutorial/lesson15.html]this[/rul] and/or this.

[/QUOTE]

the code

**yxunomei** · 10-14-2006

did u mean the start of the 2nd call of addElement?

the if statement in addElement fail, because the second time u feed addElement with *start in main, *start isn't NULL anymore, therefore it gets to the else case

**whiteflags** · 10-14-2006

Code:

void addElement (charNode **start, const char *petName)
{
   charNode *temp = newNode(petName); /* assuming this works. */

   if ( *start == NULL )
      *start = temp;
   else
   {
      temp->next = (*start)->next;
      (*start)->next = temp;
      printf(" %s ", temp->petsName);
   }
   return;
}

I think that's all that you need. I don't know why you are passing things the way you are, but I'm not making it my business.

**Axel** · 10-14-2006

yep i understand that perfectly but

in this line of code:

Code:

prev = loc;

takes loc's reference and asssigns it to prev.. so they both point to start because at the satrt of the else statement :

Code:

loc = *start;

**yxunomei** · 10-14-2006

but in the for loop, loc moves and stops once it reached the end of the list yes?

Code:

for (i=0; loc != NULL; i++)

and there's this statement at the end of the for loop (the one u were asking)

Code:

prev = loc;

it says, hey prev, copy whatever address loc has, and then the next statement

Code:

loc = loc->next;

loc moves, but prev stays where it was

**ssharish2005** · 10-14-2006

Code:

void insertnode(struct node **head, char *data)
{
    struct node *newnode =  getnode();
    struct node *Tempnode;
    
    strcpy(newnode->data,data);
    newnode->next = NULL;
    
    if(*head == NULL)
        *head = newnode;
    else
    {
        Tempnode = *head;
        
        while(Tempnode->next != NULL)
                Tempnode = Tempnode->next;
        
        Tempnode->next = newnode;
    }
}

here is sample code which will help you in understanding the concept. go though it again and again. Find the diff of what u have done and what i have done.

ssharish2005

**whiteflags** · 10-14-2006

When you insert a node into a singly linked list, you only need to adjust the next pointers at the two adjoining locations of oldItem and newItem. There shouldn't really be a need to use for loops or anything like that unless addElement is trying to do something that I'm not aware of.

I think the for loop is messing up everything. If I wanted to insert a node in the middle of your list, things would get really interesting.

**yxunomei** · 10-14-2006

I think the thread starter wanted to append item to the list already there... therefore, addElement only care about getting into the last thing in the list, and appending the new element....

**sangken** · 10-14-2006

isnt a loop necessary to traverse the list till you find where you want to insert?

**whiteflags** · 10-14-2006

No. Typically, you could just pass a pointer to where you want to insert something instead. And then pass a pointer to whatever "something" is and it can be done.

Continuing with the example that makes nodes, however:

Code:

addElement(head->next, "second item");

**Axel** · 10-14-2006

guys,

thanks alot most of the hints helped alot. With ssharish's code its somewhat more easier to follow maybe because it has less variables and more meaningful variable names? and essentially my code does the same thingn... it keeps looping till the end and checks if the nodes next element is not null till we find one thats null so we can insert the new node? am i right?

Originally Posted by ssharish2005

Code:

void insertnode(struct node **head, char *data)
{
    struct node *newnode =  getnode(); // assume that getnode is a function that malloc's a new node and returns a reference.
    struct node *Tempnode; 
    
    strcpy(newnode->data,data); // insert some data into the struct
    newnode->next = NULL; // set the new nodes proceeding node to null so we don't run into endless loops..
    
    if(*head == NULL) // this will be used only for the first element.
        *head = newnode;
    else
    {
        Tempnode = *head; // set tempnode to point to head (the start of the list)
        
        while(Tempnode->next != NULL)
                Tempnode = Tempnode->next; // here we just scan through the whole list till we reach the end (NULL)
        
        Tempnode->next = newnode; // we then insert the new node
    }
}

**whiteflags** · 10-14-2006

If you're implying that how you name variables is bad, I don't think so. However, I do notice that ssharish's code is consistant in indentation. That can do wonders for legibility.

Thread: i can't seem to understand the logic behind linked lists :|

Thread Tools

Search Thread

Display

i can't seem to understand the logic behind linked lists :|

Similar Threads

Linked Lists 101

Map file formats and linked lists

need help w/ linked lists

doubly linked lists